#include <malloc.h>
#include <stdio.h>
#include "bsf.h"

int getBsfLength(){
    return count;
}

int isBsfEmpty(){
    return count == 0;
}



void insertBSF(int key,int value){
    root = __insertBSF(root, key, value);
}

static Node* __insertBSF(Node* node,int key, int value){
    if(node == NULL){
        count ++;
        node = (Node*)malloc(sizeof(Node));
        node -> key = key;
        node -> value = value;
        node -> lChild = NULL;
        node -> rChild = NULL;
        return node;
    }
    if((node -> key) > key){
        node -> lChild =   __insertBSF(node->lChild,key,value);
    }else if ((node -> key) < key){
        node -> rChild = __insertBSF(node->rChild,key,value);
    } else {
        //更新 value值
        node -> value = value;
    }
    return node;
}

int searchBSF(int key){
    return __searchBSF(root, key);
}

static int __searchBSF(Node* node,int key){
    if(node == NULL){
        return -1;
    }
    if((node -> key) > key){
        return  __searchBSF(node->rChild,key);
    }else if ((node -> key) <  key){
        return  __searchBSF(node->lChild,key);
    } else {
        return node -> value;
    }
}

void destroyBSF(){
    __destroyBSF(&root);
}

void travelBSF(){
    __travelBSF(root);
    __travelBSF1(root);
}

static void __travelBSF(Node* node){
    if(node != NULL){
        __travelBSF(node -> lChild);
        printf("key:%d ----- > value:%d\n",node->key, node -> value);
        __travelBSF(node -> rChild);
    }
}

/**
 * 二叉树的非递归遍历
 * @param node
 */
static void __travelBSF1(Node* node){
    if (node != NULL){
        int top = -1;
        Node* stack[MAXSIZE];
        Node* p = node;
        while (top != -1 || p != NULL){
            while (p  != NULL){
                stack[++top] = p ;
                p = p -> lChild;
            }
            if (top != -1){
                p = stack[top--];
                printf("key:%d  BSF ----- > value:%d\n",p->key,p->value);
                p = p -> rChild;
            }
        }
    }
}

static void __destroyBSF(Node** node){
    if( *node != NULL ){
        __destroyBSF( &((*node)->lChild));
        __destroyBSF( &((*node)->rChild));
        free(*node);
        *node = NULL;
        count --;
    }
}

int deleteBSF(int key){
    return __deleteBSF(&root, key);
}

static int __deleteBSF(Node** node,int key){

    if(*node == NULL){
        return -1;
    }

    if(((*node) -> key) == key) {
       if ((*node) -> lChild == NULL) {
            Node *temp = *node;
            *node = (*node) ->rChild;
            int data = temp->key;
            count--;
            free(temp);
            return data;
        } else if ((*node) ->rChild == NULL) {
            Node* temp = *node;
            *node = (*node) -> lChild;
            int data = temp->key;
            count--;
            free(temp);
            return data;
        } else {
            int data;
            Node* temp = *node;
            Node *p = (*node) ->lChild;
            while (p->rChild) {
                temp = p;
                p = p->rChild;
            }
            (*node)->key = p->key;
            (*node)->value = p->value;
            if (temp != *node) {
                temp->rChild = p ->lChild;
            } else {
                temp->lChild = p ->lChild;
            }
            data = p->key;
            count--;
            p = NULL;
            free(p);
            return data;
        }
    }else if(key < ((*node) -> key)){
        return  __deleteBSF(&(*node) ->lChild,key);
    }else{
        return  __deleteBSF(&(*node) ->rChild,key);
    }
}

